package hot_100;

import java.util.Collections;
import java.util.PriorityQueue;

public class 合并K个升序链表 {
    public static void main(String[] args) {

    }

    //小根堆
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> {
            return a.val - b.val;
        });
        for (ListNode list : lists) {
            while (list != null) {
                queue.add(list);
                list = list.next;
            }
        }
        ListNode ans = new ListNode();
        ListNode net = ans;
        while (!queue.isEmpty()) {
            ListNode listNode = queue.poll();
            net.next = listNode;
            net = listNode;
        }
        net.next = null;
        return ans.next;
    }


    // 我的方法 归并排序
//    public ListNode[] ans;
//
//    public ListNode mergeKLists(ListNode[] lists) {
//        int n = lists.length;
//        ans = lists;
//        if (n == 0)
//            return null;
//        return slove(0, n - 1);
//    }
//
//    public ListNode slove(int l, int r) {
//        if (l == r)
//            return ans[l];
//        int mid = (l + r) >> 1;
//        ListNode lc = slove(l, mid);
//        ListNode rc = slove(mid + 1, r);
//        ListNode ans = new ListNode();
//        ListNode temp = ans;
//        while (lc != null && rc != null) {
//            ListNode net = new ListNode();
//            if (lc.val <= rc.val) {
//                net.val = lc.val;
//                lc = lc.next;
//            } else {
//                net.val = rc.val;
//                rc = rc.next;
//            }
//            temp.next = net;
//            temp = net;
//        }
//        while (lc != null) {
//            ListNode net = new ListNode(lc.val);
//            lc = lc.next;
//            temp.next = net;
//            temp = net;
//        }
//        while (rc != null) {
//            ListNode net = new ListNode(rc.val);
//            rc = rc.next;
//            temp.next = net;
//            temp = net;
//        }
//        return ans.next;
//    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
